public class EightQueensProblem {
    static int size = 8; // 棋盘大小 8x8
    static int[] queens = new int[size]; // queens[i] = 第i行皇后放在第几列
    static int count = 0; // 解的个数

    public static void main(String[] args) {
        solve(0); // 从第0行开始摆放
        System.out.println("总共有 " + count + " 种解法。");
    }

    // 放置皇后
    public static void solve(int row) {
        if (row == size) {
            print(); // 找到一种解，打印出来
            count++;
            return;
        }

        for (int col = 0; col < size; col++) {
            if (isSafe(row, col)) {
                queens[row] = col; // 在第row行放置皇后，列为col
                solve(row + 1); // 递归放置下一行
                // 不需要显式撤销，下一次循环直接覆盖 queens[row]
            }
        }
    }

    // 判断第row行第col列是否安全
    public static boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 不能同列 或 对角线
            if (queens[i] == col || Math.abs(i - row) == Math.abs(queens[i] - col)) {
                return false;
            }
        }
        return true;
    }

    // 打印棋盘
    public static void print() {
        System.out.println("解法 " + (count + 1) + ":");
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}